#include <iostream>

using namespace std;

int T;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

bool check(int a, int x, int y)
{
    return !(a & x) || !(a & y)
         ||!(a ^ x) || !(a ^ y)
         ||!(gcd(a, y)) || !(gcd(a, x));
}

int main()
{
    cin >> T;
    while(T--)
    {
        int x, y; cin >> x >> y;
        if(!(x & y) || !(x | y) || !(x ^ y) || !(gcd(x, y)))
        {
            cout << 1 << endl;
        }
        else
        {
            int a = x & y;
            int b = x ^ y;
            int c = gcd(x, y);
            if(check(a, x, y) || check(b, x, y) || check(c, x, y))
            {
                cout << 2 << endl;
            }
            else
            {
                cout << 3 << endl;
            }
        }
    }
    return 0;
}
